package com.LeeCode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 数据流的中位数
 */

public class Code295 {
    public static void main(String[] args) {
        MedianFinder medianFinder = new Code295().new MedianFinder();
//        medianFinder.addNum(-1);
//        System.out.println(medianFinder.findMedian());
//        medianFinder.addNum(-2);
//        System.out.println(medianFinder.findMedian());
//        medianFinder.addNum(-3);
//        System.out.println(medianFinder.findMedian());
//        medianFinder.addNum(-4);
//        System.out.println(medianFinder.findMedian());
//        medianFinder.addNum(-5);
//        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());


    }

    class MedianFinder {

        private PriorityQueue<Integer> bigger;
        private PriorityQueue<Integer> smaller;
        private int count;

        public MedianFinder() {
            bigger = new PriorityQueue<>();
            smaller = new PriorityQueue<>(Comparator.reverseOrder());
            count = 0;
        }

        public void addNum(int num) {
            if (count % 2 == 0) { // 偶数
                if(count == 0){
                    bigger.offer(num);
                    count++;
                    return;
                }
                int big = num > smaller.peek() ? num : smaller.peek();
                int small = num < smaller.peek() ? num : smaller.peek();
                bigger.offer(big);
                smaller.poll();
                smaller.offer(small);
            } else {  // 奇数
                int big = num > bigger.peek() ? num : bigger.peek();
                int small = num < bigger.peek() ? num : bigger.peek();
                smaller.offer(small);
                bigger.poll();
                bigger.offer(big);
            }
            count++;
        }

        public double findMedian() {
            int m1 = smaller.isEmpty() ? 0 : smaller.peek();
            int m2 = bigger.isEmpty() ? 0 : bigger.peek();
            if (count % 2 == 0) {
                return (m1 + m2) / 2.0;
            } else {
                return m2;
            }
        }
    }
}
